package 排序算法.快速排序;

import java.util.Arrays;

/**
 * @Project: data-structure-and-algorithms
 * @Package: 排序.快速排序
 * @ClassName: DualPivotQuickSort
 * @Author: zhouyihe
 * @Date: 2025/11/5 14:07
 * @Description: 双轴快速排序--快速排序(迭代)的优化
 */
public class DualPivotQuickSort {
    /**
     * Java 的 Arrays.sort() 使用的是双轴快速排序，它使用两个枢轴(基准)，可以进一步提高性能
     *
     * @param arr
     * @param low
     * @param high
     */
    public static void dualPivotQuickSort(int[] arr, int low, int high) {
        if (high <= low) {
            return;
        }

        // 如果arr[low] > arr[high]，则交换
        if (arr[low] > arr[high]) {
            int temp = arr[low];
            arr[low] = arr[high];
            arr[high] = temp;
        }

        // 获取两个枢轴
        int pivot1 = arr[low];
        int pivot2 = arr[high];

        // 小于pivot1的区域右边界
        int lt = low + 1;
        // 大于pivot2的区域左边界
        int gt = high - 1;
        // 当前考察的元素
        int i = low + 1;

        while (i <= gt) {
            // 当前元素小于第一个驱轴pivot1
            if (arr[i] < pivot1) {
                int temp = arr[lt];
                arr[lt] = arr[i];
                arr[i] = temp;
                lt++;
                i++;
            }
            // 当前元素大于第二个驱轴pivot2
            else if (arr[i] > pivot2) {
                int temp = arr[i];
                arr[i] = arr[gt];
                arr[gt] = temp;
                gt--;
            }
            // 当前元素在两个轴之间
            else {
                i++;
            }
        }

        // 将驱轴放到正确的位置
        arr[low] = arr[lt - 1];
        arr[lt - 1] = pivot1;

        arr[high] = arr[gt + 1];
        arr[gt + 1] = pivot2;

        // 递归三个区域
        dualPivotQuickSort(arr, low, lt - 2);
        dualPivotQuickSort(arr, lt, gt);
        dualPivotQuickSort(arr, gt + 2, high);

    }

    public static void main(String[] args) {
        int[] arr = {3,2,1,5,6,4};
        dualPivotQuickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }
}
